#include <stdio.h>
#include <stdlib.h>

typedef struct Graph{
    char *vexs;
    int **arcs;
    int vexNum;
    int arcNum;
} Graph;

#define MAX 32767 

typedef struct Edge{
    int start;
    int end;
    int weight;
} Edge;

Edge *initEdge(Graph *G) 
{
    int index = 0; //边数组索引
    Edge *edge = (Edge *)malloc(sizeof(Edge) * G->arcNum);
    //二重循环赋值 
    for (int i = 0; i < G->vexNum; i++) { 
        for (int j = i + 1; j < G->vexNum; j++) { //此处排除自己和自己
            if (G->arcs[i][j] != MAX) {
                edge[index].start = i;
                edge[index].end = j;
                edge[index].weight = G->arcs[i][j];
                index++;
            }
        }
    }
    return edge;
}
//基于冒泡
void sortEdge (Edge *edge, Graph *G) 
{
    Edge temp;
    for (int i = 1; i < G->arcNum; i++) {
        for (int j = 0; j < G->arcNum-i; j++) {
            if (edge[j].weight > edge[j+1].weight) {
                temp = edge[j];
                edge[j] = edge[j+1];
                edge[j+1] = temp;     
            }
        }
    }
}

void kruskal(Graph *G)
{
    Edge *edge = initEdge(G);
    sortEdge(edge, G);
    int *connected = (int *)malloc(sizeof(int) * G->vexNum);
    for (int i = 0; i < G->vexNum; i++) {//连通分量数组初始化
        connected[i] = i;
    }
    for (int i = 0; i < G->arcNum; i++) {
        int start = connected[edge[i].start];
        int end   = connected[edge[i].end];
        if (start != end) { //连通分量不同时连接
            printf("v%c --> v%c weight=%d\n", G->vexs[edge[i].start], G->vexs[edge[i].end], edge[i].weight);
        }
        for (int j = 0; j < G->vexNum; j++) {
            if (connected[j] == end) {//更新连通分量
                connected[j] = start;
            }
        }
    }
}

Graph *initGraph(int vexNum) //顶点数
{
    Graph *G = (Graph *)malloc(sizeof(Graph));
    G->arcs = (int **)malloc(sizeof(int *) * vexNum);
    G->vexs = (char *)malloc(sizeof(char) * vexNum);
    for (int i = 0; i < vexNum; i++) {
        G->arcs[i] = (int *)malloc(sizeof(int) * vexNum);
    }
    G->arcNum = 0;
    G->vexNum = vexNum;
    return G;
}

void creatGraph(Graph *G, char *vexs, int *arcs)
{
    for (int i = 0; i < G->vexNum; i++) {
        G->vexs[i] = vexs[i];
        for (int j = 0; j < G->vexNum; j++) { //注意此时只是普通的二级指针
            G->arcs[i][j] = *(arcs + i * G->vexNum + j);
            if (G->arcs[i][j] != 0 && G->arcs[i][j] != MAX) {
                G->arcNum++;
            }
        }
    }
    G->arcNum /= 2;
}

void DFS(Graph *G, int *visited, int index) //索引第一个节点开始
{
    printf("%c ", G->vexs[index]);//访问
    visited[index] = 1;
    for (int i = 0; i < G->vexNum; i++) {
        if (G->arcs[index][i] > 0 && G->arcs[index][i] != MAX && !visited[i]) {//遍历 + 递归
            DFS(G, visited, i);
        }
    }
}

int main(void)
{    
    Graph* G = initGraph(6);
    int* visited = (int*)malloc(sizeof(int) * G -> vexNum);
    for (int i = 0; i < G -> vexNum; i++)
        visited[i] = 0;
    int arcs[6][6] = {
            0, 6, 1, 5, MAX, MAX,
            6, 0, 5, MAX, 3, MAX,
            1, 5, 0, 5, 6, 4,
            5, MAX, 5, 0, MAX, 2,
            MAX, 3, 6, MAX, 0, 6,
            MAX, MAX, 4, 2, 6, 0
    };
    creatGraph(G, "123456", (int*)arcs);
    DFS(G, visited, 0);
    printf("\n");
    kruskal(G);
    return 0;
}